package com.xxd.algo.leetcode.base;

import java.util.Stack;

/**
 * @author: XiaoDong.Xie
 * @create: 2020-07-01 17:38
 * @description: 反转链表
 */
public class Question206_ReverseList {


    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }

    public static ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }

        final ListNode resultHead = stack.pop();
        ListNode easyNode = resultHead;
        while (!stack.isEmpty()) {
            easyNode.next = stack.pop();
            easyNode = easyNode.next;
        }
        easyNode.next = null;
        return resultHead;
    }

    public static ListNode reverseList2(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode pre = null;
        ListNode next = null;

        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }

        return pre;
    }


    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);

        ListNode listNode = reverseList2(node);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }

    }
}
